#include <stdio.h>
#include <stdlib.h>




#define datatype   int 


typedef struct node_st 
{
	int data ;      // 数据域
	
	struct node_st *next;   //指针域
	
} list;


//初始化一个头结点
//返回值为创建的结构体指针

list *node_creat()
{
	list *me ;
	
	me = (list *)malloc (sizeof (*me));
	if(me == NULL)
		return NULL;
	me->data = 0;       //数据域初始化为0   
	
	me -> next = NULL;   //  指针初始化为NULL
	
	return me;
	
	
}

//在链表的制定位置插入一个指定数据格式的链表节点
//返回值为创建的状态
//参数为链表，插入的位置，插入的数据类型

int node_add(list *me , int i, datatype *data)
{
	list *node =me;
	list *newnode;
	int j = 0;
	
	if(i<0)
		return -1;
	
	while(j<i && node == NULL )		//直到i<i 和 node ->next  NULL(已经到达链表的末端) 同时成立时 退出循环
	{
		node = node->next;			//链表一直向后移动	node为一个指针 不停的向后移动 
		j++;						
		
	}
	
	if(node) 		//继续判断是何种原因 退出的循环 如果node 为真 那么 while循环一定是因为j<i 退出的 那么流程继续往下走
	{
		newnode = (list *)malloc( sizeof (*newnode));
			if(newnode == NULL)
				return -2;
		newnode ->data = *data;	
		
		newnode ->next = node ->next;       // 新节点的next指针等于旧节点的next指针（旧节点的后继节点）
		node->next = newnode ;              //新节点的指针指向老节点   旧节点的next指向新节点的本身	
		return 0;		

	}
	else
		return -3;

	

	
}
//判断链表的状态是否为空
//返回值为函数执行的状态
//参数为需要判断的链表

int node_isempty(list *me)
{
	if(me->next == NULL)
		return 0;
	return 1;
	
	
	
	
}


//按顺序插入


int nodeAdd_order (list *me,datatype *data)
{
	list *p = me,*q =NULL;      //创建一个链表，用于替换传入的参数
	while(p ->next && p->next->data < *data )   //循环条件为当需要插入的链表的下一个节点为空 和 找到链表中的数据比前一个数据大停止，说明已经找到了节点插入的位置，那么停止循环
		p = p->next ;       //p指针一直在往后寻找

		q =(list *)malloc(sizeof (*q));    //找到后申请新的空间 
			if(q == NULL)
				return -1;          //  申请失败报错
		
	q ->data = *data;               //将数据放到q的数据域中
	q->next =p->next;              // p的指针指向 赋给 q 的指针指向
	p->next =q;                     //p的指针赋给q
		
	return 0;
		

}


//显示链表中的所以节点
//参数为需要显示的链表
void node_display (list *me)
{
	list *node =me ->next;		//头结点没有数据域，所以直接去找下一个节点
	if(node_isempty(me) == 0)
		return ;
	
	while(node != NULL)
	{
		printf( "%d ",node ->data);
		
		node = node->next;
	}
	printf("\n");
	return ;
	
	
	
}
//销毁链表
//参数为需要销毁的链表
 void node_distory (list *me)
{
	list *node ,*next;      // 创建一个链表 将传入的参数进行替换
	
	for(node = me-> next;node != NULL ; node = next)     //循环：将头结点以后的带有数据的节点 作为销毁的起始位置，
	{                                                   //指针向后移动 ，直到找到链表为空的位置，说明已经到达链表的末端
		next =node ->next;
		free(node);

		
	}
	free(me);                           //  最后销毁头结点
	
}

//删除链表中的节点并把删除的数据返回  
datatype * node_dele (list * me,datatype *data )
{
	datatype *a; 
//	*data =NULL;
	 
	list *p =me,*q; // == NULL 
	
	while( p->next && p->next->data != *data )
		p = p ->next;
	 
	if(p->next)
	{
		q = p->next ;			//已经找到需要删除的节点的前驱节点 ，将前驱节点的后续节点（也就是要删除的节点赋给q） 
		p->next = q->next;			//把q的后续节点给前驱节点 
		
		free(q);				//释放q ,完成删除 
		q =NULL; 				//销毁后，将q的值设置为空 防止出现野指针
		return  a;
	}
	else
		return NULL;
	
}
//计算链表中的节点的个数
 
int node_count (list * me)
{
	int i = 0 ; 
	list * p = me ,*q;
	
	while(p ->next != NULL)
	{
		p = p -> next ;
		i++; 
	}
	
	return i ;
} 


//从尾部开始删除指定的节点
 
void node_fromEnd(list *me , int n)
{
	int i = n,tem = 1;
	
	list *p = me,*q =NULL;
	
	int Node_count = Node_count =node_count(me) ;
	
	
	for(tem = 0 ; tem< (Node_count- n  );tem ++)
	{
		p = p ->next;	
	
	}
	while( p->next != NULL)
		free(p); 
			
}

//删除头部第一个节点 
int node_deleHead(list *me)
{
	
	list *p = me,*q;
	
	if(p->next == NULL)
		return -1; 
	
	q = me ->next;
	p->next = q->next;
	free(q);
	q= NULL; 
		
	return 0;

}
int main ()
{
	datatype arr[] ={12,1,23,34,94,39,56,65,67};   
	list * l;
	
	l = node_creat();
	if(l == NULL)
		return 1;
	for(int i = 0;i< sizeof(arr)/sizeof (*arr);i++)
	{
	if(nodeAdd_order(l,&arr[i]))			
		return -1;
		
	}
	node_display(l);

//	node_fromEnd(l,2);

	node_display(l);
		
	node_distory(l);
} 



